{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Stepping Numbers in Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSteppingNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计范围内的步进数字数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数&nbsp;<code>low</code> 和&nbsp;<code>high</code>&nbsp;，都用字符串表示，请你统计闭区间 <code>[low, high]</code>&nbsp;内的 <strong>步进数字</strong>&nbsp;数目。</p>\n",
    "\n",
    "<p>如果一个整数相邻数位之间差的绝对值都 <strong>恰好</strong>&nbsp;是 <code>1</code>&nbsp;，那么这个数字被称为 <strong>步进数字</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个整数，表示闭区间&nbsp;<code>[low, high]</code>&nbsp;之间步进数字的数目。</p>\n",
    "\n",
    "<p>由于答案可能很大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p><b>注意：</b>步进数字不能有前导 0 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>low = \"1\", high = \"11\"\n",
    "<b>输出：</b>10\n",
    "<strong>解释：</strong>区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>low = \"90\", high = \"101\"\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>区间 [90,101] 内的步进数字为 98 和 101 。总共有 2 个步进数字。所以输出为 2 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= int(low) &lt;= int(high) &lt; 10<sup>100</sup></code></li>\n",
    "\t<li><code>1 &lt;= low.length, high.length &lt;= 100</code></li>\n",
    "\t<li><code>low</code> 和&nbsp;<code>high</code>&nbsp;只包含数字。</li>\n",
    "\t<li><code>low</code> 和&nbsp;<code>high</code>&nbsp;都不含前导 0 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-stepping-numbers-in-range](https://leetcode.cn/problems/count-stepping-numbers-in-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-stepping-numbers-in-range](https://leetcode.cn/problems/count-stepping-numbers-in-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1\"\\n\"11\"', '\"90\"\\n\"101\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def step_count(start, N):\n",
    "    if N == 0:\n",
    "        return 1\n",
    "    if start < 0 or start > 9:\n",
    "        return 0\n",
    "    ans = 0\n",
    "    if start > 0:\n",
    "        ans += step_count(start - 1, N - 1)\n",
    "    if start < 9:\n",
    "        ans += step_count(start + 1, N - 1)\n",
    "    print(\"step_count\", start, N, ans)\n",
    "    return ans % 1000000007\n",
    "\n",
    "@cache\n",
    "def strict_less(start, N):\n",
    "    if N == 0:\n",
    "        return start - 1\n",
    "    ans = strict_less(10, N - 1)\n",
    "    for i in range(1, start):\n",
    "        ans += step_count(i, N)\n",
    "    return ans % 1000000007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        def total(limit):\n",
    "            ans = strict_less(ord(limit[0]) - ord('0'), len(limit) - 1)\n",
    "            N = len(limit)\n",
    "            for i in range(N):\n",
    "                start = ord(limit[i]) - ord('0')\n",
    "                if i == N - 1 or ord(limit[i + 1]) - ord('0') > start + 1:\n",
    "                    ans += step_count(start, N - i - 1)\n",
    "                    break\n",
    "                elif ord(limit[i + 1]) - ord('0') == start + 1:\n",
    "                    if start > 0:\n",
    "                        ans += step_count(start - 1, N - i - 2)\n",
    "                elif ord(limit[i + 1]) - ord('0') == start:\n",
    "                    if start > 0:\n",
    "                        ans += step_count(start - 1, N - i - 2)\n",
    "                    break\n",
    "                elif ord(limit[i + 1]) - ord('0') < start - 1:\n",
    "                    break\n",
    "            #print(\"total\", limit, ans)\n",
    "            return ans % 1000000007\n",
    "        return (total(high) - total(str(int(low) - 1))) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        self.MOD = 1000_000_007\n",
    "        cnt = 1\n",
    "        for i in range(1, len(low)):\n",
    "            if abs(int(low[i]) - int(low[i-1])) != 1:\n",
    "                cnt = 0\n",
    "                break\n",
    "        return (self.getCnt(high) - self.getCnt(low) + cnt) % self.MOD\n",
    "\n",
    "    def getCnt(self, high):\n",
    "        self.high = high\n",
    "        self.vis = {}\n",
    "        return self.dfs(0, -1, True)\n",
    "\n",
    "    def dfs(self, idx, last, isLimit):\n",
    "        if idx == len(self.high):\n",
    "            return 1 if last != -1 else 0\n",
    "        key = (idx, last, isLimit)\n",
    "        if key not in self.vis:\n",
    "            self.vis[key] = 0\n",
    "            digit = int(self.high[idx])\n",
    "            end = digit if isLimit else 9\n",
    "            if last == -1:\n",
    "                self.vis[key] += self.dfs(idx+1, -1, False)\n",
    "                for i in range(1, end):\n",
    "                    self.vis[key] = (self.vis[key] + self.dfs(idx+1, i, False)) % self.MOD\n",
    "                self.vis[key] = (self.vis[key] + self.dfs(idx+1, end, isLimit)) % self.MOD\n",
    "            else:\n",
    "                if 0 <= last-1 <= end:\n",
    "                    self.vis[key] = (self.vis[key] + self.dfs(idx+1, last-1, isLimit and last-1==digit)) % self.MOD\n",
    "                if 0 <= last+1 <= end:\n",
    "                    self.vis[key] = (self.vis[key] + self.dfs(idx+1, last+1, isLimit and last+1==digit)) % self.MOD\n",
    "        return self.vis[key]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        def dp(n):\n",
    "            s = str(n)\n",
    "            @cache\n",
    "            def cau(idx, isNumb, isLimit, pre):\n",
    "                if idx == len(s):\n",
    "                    return int(isNumb)\n",
    "                res = 0 if isNumb else cau(idx + 1, False, False, pre)\n",
    "                lim = int(s[idx]) if isLimit else 9\n",
    "                for i in range(lim + 1):\n",
    "                    if not isNumb and i == 0:\n",
    "                        continue\n",
    "                    if abs(pre - i) == 1 or not isNumb:\n",
    "                        res += cau(idx + 1, True, isLimit and (i == int(s[idx])), i)\n",
    "                return res % (10**9+7)\n",
    "            ans = cau(0, False, True, 0)\n",
    "            # print(ans)\n",
    "            cau.cache_clear()\n",
    "            return ans\n",
    "        return (dp(int(high)) - dp(int(low) - 1)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, pre, islimit, isnum):\n",
    "            if i == n:\n",
    "                return isnum\n",
    "            cnt = dfs(i + 1, pre, 0, 0) if not isnum else 0\n",
    "            digit = int(s[i])\n",
    "            ub = digit if islimit else 9\n",
    "            for d in range(1 - isnum, ub + 1):\n",
    "                if pre == -1:\n",
    "                    cnt = (cnt + dfs(i + 1, d, islimit and d == digit, 1)) % mod\n",
    "                else:\n",
    "                    if abs(d - pre) == 1:\n",
    "                        cnt = (cnt + dfs(i + 1, d, islimit and d == digit, 1)) % mod\n",
    "            return cnt\n",
    "\n",
    "        s = str(int(low) - 1)\n",
    "        n = len(s)\n",
    "        l = dfs(0, -1, 1, 0)\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        s = high\n",
    "        n = len(s)\n",
    "        r = dfs(0, -1, 1, 0)\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        return (r - l + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, pre, islimit, isnum):\n",
    "            if i == n:\n",
    "                return isnum\n",
    "            cnt = dfs(i + 1, pre, 0, isnum) if not isnum else 0\n",
    "            digit = int(s[i])\n",
    "            ub = digit if islimit else 9\n",
    "            for d in range(1 - isnum, ub + 1):\n",
    "                if pre == -1:\n",
    "                    cnt = (cnt + dfs(i + 1, d, islimit and d == digit, 1)) % mod\n",
    "                else:\n",
    "                    if abs(d - pre) == 1:\n",
    "                        cnt = (cnt + dfs(i + 1, d, islimit and d == digit, 1)) % mod\n",
    "            return cnt\n",
    "\n",
    "        s = str(int(low) - 1)\n",
    "        n = len(s)\n",
    "        l = dfs(0, -1, 1, 0)\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        s = high\n",
    "        n = len(s)\n",
    "        r = dfs(0, -1, 1, 0)\n",
    "        dfs.cache_clear()\n",
    "        \n",
    "        return (r - l + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: str):\n",
    "            m = len(s)\n",
    "            dp = [[-1] * 10 for _ in range(m)]\n",
    "            # @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return int(is_num)\n",
    "                if not is_limit and is_num and dp[i][pre] != -1:\n",
    "                    return dp[i][pre]\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[i]) if is_limit else 9\n",
    "                for d in range(l, r + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res = (res + f(i + 1, d, is_limit and (d == int(s[i])), True)) % MOD\n",
    "                if not is_limit and is_num:\n",
    "                    dp[i][pre] = res\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return ((cal(high) - cal(str(int(low) - 1))) % MOD + MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: str):\n",
    "            m = len(s)\n",
    "            dp = [[-1] * 10 for _ in range(m)]\n",
    "            # @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return int(is_num)\n",
    "                if not is_limit and is_num and dp[i][pre] != -1:\n",
    "                    return dp[i][pre]\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[i]) if is_limit else 9\n",
    "                for d in range(l, r + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res = (res + f(i + 1, d, is_limit and (d == int(s[i])), True)) % MOD\n",
    "                if not is_limit and is_num:\n",
    "                    dp[i][pre] = res\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return ((cal(high) - cal(str(int(low) - 1))) % MOD + MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: str):\n",
    "            m = len(s)\n",
    "            dp = [[-1] * 10 for _ in range(m)]\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return int(is_num)\n",
    "                if not is_limit and is_num and dp[i][pre] != -1:\n",
    "                    return dp[i][pre]\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[i]) if is_limit else 9\n",
    "                for d in range(l, r + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res = (res + f(i + 1, d, is_limit and (d == int(s[i])), True)) % MOD\n",
    "                if not is_limit and is_num:\n",
    "                    dp[i][pre] = res\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return ((cal(high) - cal(str(int(low) - 1))) % MOD + MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: str):\n",
    "            m = len(s)\n",
    "            dp = [[-1] * 10 for _ in range(m)]\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return int(is_num)\n",
    "                if not is_limit and is_num and dp[i][pre] != -1:\n",
    "                    return dp[i][pre]\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[i]) if is_limit else 9\n",
    "                for d in range(l, r + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res = (res + f(i + 1, d, is_limit and (d == int(s[i])), True)) % MOD\n",
    "                if not is_limit and is_num:\n",
    "                    dp[i][pre] = res\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return ((cal(high) - cal(str(int(low) - 1))) % MOD + MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        n = len(high)\n",
    "        low = low.zfill(n)\n",
    "        mod = 10 ** 9 + 7\n",
    "        @ cache\n",
    "        def dp(i, pre, low_limit, high_limit, is_zero):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if is_zero:\n",
    "                for digit in range(10):\n",
    "                    if (not low_limit or int(low[i]) <= digit) and (not high_limit or digit <= int(high[i])):\n",
    "                        res += dp(i+1, digit, low_limit and digit == int(low[i]), high_limit and digit == int(high[i]), digit == 0)\n",
    "            else:\n",
    "                \n",
    "                if pre >0 and (not low_limit or pre - 1 >= int(low[i])) and (not high_limit or pre - 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre-1, low_limit and pre - 1 == int(low[i]), high_limit and pre - 1 == int(high[i]), False)\n",
    "                if pre < 9 and (not low_limit or pre + 1 >= int(low[i])) and (not high_limit or pre + 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre + 1, low_limit and pre + 1 == int(low[i]), high_limit and pre + 1 == int(high[i]), False)\n",
    "            return res % mod        \n",
    "        return dp(0, 0, True, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        n = len(high)\n",
    "        low = low.zfill(n)\n",
    "        mod = 10 ** 9 + 7\n",
    "        @ cache\n",
    "        def dp(i, pre, low_limit, high_limit, is_zero):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if is_zero:\n",
    "                for digit in range(10):\n",
    "                    if (not low_limit or int(low[i]) <= digit) and (not high_limit or digit <= int(high[i])):\n",
    "                        res += dp(i+1, digit, low_limit and digit == int(low[i]), high_limit and digit == int(high[i]), digit == 0)\n",
    "            else:\n",
    "                \n",
    "                if pre >0 and (not low_limit or pre - 1 >= int(low[i])) and (not high_limit or pre - 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre-1, low_limit and pre - 1 == int(low[i]), high_limit and pre - 1 == int(high[i]), False)\n",
    "                if pre < 9 and (not low_limit or pre + 1 >= int(low[i])) and (not high_limit or pre + 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre + 1, low_limit and pre + 1 == int(low[i]), high_limit and pre + 1 == int(high[i]), False)\n",
    "            return res % mod        \n",
    "        return dp(0, 0, True, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        #dp1[idx][stat][bound]\n",
    "        dp=[[[0]*2 for _ in range(11)] for __ in range(len(low))]\n",
    "        \n",
    "        larr=[]\n",
    "        M=1000000007\n",
    "        for i in range(len(low)):\n",
    "            larr.append(ord(low[i])-ord('0'))\n",
    "        def dfs1(idx,stat,bound,arr):\n",
    "            if idx==len(arr):\n",
    "                return 1\n",
    "            nonlocal M,dp\n",
    "            if dp[idx][stat][bound]!=0:\n",
    "                return dp[idx][stat][bound]\n",
    "            res=0\n",
    "            if stat>=1 and stat<=8:\n",
    "                if stat+1<=arr[idx] or bound==0:\n",
    "                    res=dfs1(idx+1,stat+1,1 if (stat+1==arr[idx])and bound==1 else 0,arr)\n",
    "                if stat-1<=arr[idx] or bound==0:\n",
    "                    res+=dfs1(idx+1,stat-1,1 if (stat-1==arr[idx])and bound==1 else 0,arr)\n",
    "            elif stat==0:\n",
    "                if 1<=arr[idx] or bound==0:\n",
    "                    res=dfs1(idx+1,1,1 if (1==arr[idx])and bound==1 else 0,arr)\n",
    "            elif stat==9:\n",
    "                if 8<=arr[idx] or bound==0:\n",
    "                    res=dfs1(idx+1,8,1 if (8==arr[idx])and bound==1 else 0,arr)\n",
    "            elif stat==10:\n",
    "                for i in range(1,11):\n",
    "                    res+=dfs1(idx+1,i,0,arr)\n",
    "            dp[idx][stat][bound]=res%M\n",
    "            return res%M\n",
    "        res1=-1\n",
    "        for i in range(1,len(larr)):\n",
    "            if abs(larr[i]-larr[i-1])!=1:\n",
    "                res1=0\n",
    "                break\n",
    "        res2=0\n",
    "        for i in range(1,larr[0]+1):\n",
    "            res1+=dfs1(1,i,1 if i==larr[0] else 0,larr)\n",
    "        res1+=dfs1(1,10,0,larr)\n",
    "        harr=[]\n",
    "        dp=[[[0]*2 for _ in range(11)] for __ in range(len(high))]\n",
    "        for i in range(len(high)):\n",
    "            harr.append(ord(high[i])-ord('0'))\n",
    "        for i in range(1,harr[0]+1):\n",
    "            res2+=dfs1(1,i,1 if i==harr[0] else 0,harr)\n",
    "        res2+=dfs1(1,10,0,harr)\n",
    "\n",
    "        return (res2-res1)%M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "@lru_cache(None)\n",
    "def g(lead: int, len: int) -> int:\n",
    "    if len == 1:\n",
    "        if lead == 0 or lead == 9:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2\n",
    "    else:\n",
    "        return sum(g(i, len - 1) for i in range(10) if abs(lead - i) == 1) % MOD\n",
    "    \n",
    "@lru_cache(None)\n",
    "def f(high: str, lastl: int) -> int:\n",
    "    t = int(high[0])\n",
    "    if len(high) == 1:\n",
    "        if lastl == -1:\n",
    "            return t\n",
    "        else:\n",
    "            return sum(int(abs(i - lastl) == 1) for i in range(t + 1))\n",
    "    else:\n",
    "        ret = 0\n",
    "        if lastl == -1:\n",
    "            for i in range(1, t):\n",
    "                ret += g(i, len(high) - 1)\n",
    "            ret += f('9'*(len(high) - 1), -1)\n",
    "            ret % MOD\n",
    "            ret += f(high[1:], t)\n",
    "            ret % MOD\n",
    "        else:\n",
    "            for i in range(10):\n",
    "                if abs(i - lastl) == 1:\n",
    "                    if i < t:\n",
    "                        ret += f('9' * (len(high) - 1), i)\n",
    "                        ret % MOD\n",
    "                    elif i == t:\n",
    "                        ret += f(high[1:], i)\n",
    "                        ret % MOD\n",
    "        return ret\n",
    "\n",
    "\n",
    "def f2(high: int) -> int:\n",
    "    ret = 0\n",
    "    def _f2(s):\n",
    "        a = iter(s)\n",
    "        next(a)\n",
    "        return all(abs(int(i) - int(j)) == 1 for i, j in zip(a, iter(s)))\n",
    "    for i in range(1, high + 1):\n",
    "        if _f2(str(i)):\n",
    "            ret += 1\n",
    "    return ret\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        return (f(high, -1) - f(str(int(low) - 1), -1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        n = len(high)\n",
    "        low = low.zfill(n)\n",
    "        mod = 10 ** 9 + 7\n",
    "        @ cache\n",
    "        def dp(i, pre, low_limit, high_limit, is_zero):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if is_zero:\n",
    "                for digit in range(10):\n",
    "                    if (not low_limit or int(low[i]) <= digit) and (not high_limit or digit <= int(high[i])):\n",
    "                        res += dp(i+1, digit, low_limit and digit == int(low[i]), high_limit and digit == int(high[i]), digit == 0)\n",
    "            else:\n",
    "                \n",
    "                if pre >0 and (not low_limit or pre - 1 >= int(low[i])) and (not high_limit or pre - 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre-1, low_limit and pre - 1 == int(low[i]), high_limit and pre - 1 == int(high[i]), False)\n",
    "                if pre < 9 and (not low_limit or pre + 1 >= int(low[i])) and (not high_limit or pre + 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre + 1, low_limit and pre + 1 == int(low[i]), high_limit and pre + 1 == int(high[i]), False)\n",
    "            return res % mod        \n",
    "        return dp(0, 0, True, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        n = len(high)\n",
    "        low = low.zfill(n)\n",
    "        mod = 10 ** 9 + 7\n",
    "        @ cache\n",
    "        def dp(i, pre, low_limit, high_limit, is_zero):\n",
    "            if i == n:\n",
    "                print(i, pre, low_limit, high_limit, is_zero,\"A\")\n",
    "                return 1\n",
    "            res = 0\n",
    "            print(i, pre, low_limit, high_limit, is_zero)\n",
    "            if is_zero:\n",
    "                for digit in range(10):\n",
    "                    if (not low_limit or int(low[i]) <= digit) and (not high_limit or digit <= int(high[i])):\n",
    "                        res += dp(i+1, digit, low_limit and digit == int(low[i]), high_limit and digit == int(high[i]), digit == 0)\n",
    "            else:\n",
    "                \n",
    "                if pre >0 and (not low_limit or pre - 1 >= int(low[i])) and (not high_limit or pre - 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre-1, low_limit and pre - 1 == int(low[i]), high_limit and pre - 1 == int(high[i]), False)\n",
    "                if pre < 9 and (not low_limit or pre + 1 >= int(low[i])) and (not high_limit or pre + 1 <= int(high[i])):\n",
    "                    res += dp(i+1, pre + 1, low_limit and pre + 1 == int(low[i]), high_limit and pre + 1 == int(high[i]), False)\n",
    "            return res % mod        \n",
    "        return dp(0, 0, True, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        return (self.count(high) - self.count(str(int(low) - 1))) % int(1e9 + 7)\n",
    "    \n",
    "    @staticmethod\n",
    "    def count(n):\n",
    "        k = len(n)\n",
    "        dp = [[-1] * k for i in range(11)]\n",
    "        # if prev_num == 10, not a number\n",
    "        def dfs(pos, prev_num, is_limit):\n",
    "            if pos == k:\n",
    "                return prev_num != 10\n",
    "            if not is_limit and dp[prev_num][pos] != -1:\n",
    "                return dp[prev_num][pos]\n",
    "            ans = 0\n",
    "            up = 9 if not is_limit else int(n[pos])\n",
    "            ds = [prev_num - 1, prev_num + 1]\n",
    "            if prev_num == 10:\n",
    "                ans += dfs(pos + 1, prev_num, False)\n",
    "                ds = list(range(1, 10))\n",
    "            for d in ds:\n",
    "                if 0 <= d <= up:\n",
    "                    ans += dfs(pos + 1, d, is_limit and d == int(n[pos]))\n",
    "            if not is_limit:\n",
    "                dp[prev_num][pos] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 10, True) % int(1e9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        def func(x):\n",
    "            x = list(map(int, x))\n",
    "            n = len(x) \n",
    "            @cache\n",
    "            def dfs(bit,prev,is_limit ,is_num): \n",
    "                ret = 0\n",
    "                if bit==n :\n",
    "                    return  is_num  \n",
    "                ret = 0 \n",
    "                if  is_num==0:\n",
    "                    ret = dfs(bit+1,prev,0,0)\n",
    "\n",
    "                up = x[bit] if is_limit==1 else 9 \n",
    "                low = 1 if is_num==0 else 0\n",
    "                for d in range(low,up+1):\n",
    "                    if is_num == 0 or   abs(d-prev)==1:\n",
    "                        ret += dfs(bit+1,d, int(is_limit == 1 and d==up),1)\n",
    "                return ret % MOD\n",
    "\n",
    "            return dfs(0,0,1,0) \n",
    "\n",
    "        is_low_bujin = 0\n",
    "        llll = list( map(int,low) )\n",
    "        if all( abs(a-b)==1 for a,b in zip(llll[1:],llll[:-1]) ):\n",
    "            is_low_bujin = 1\n",
    "\n",
    "        return ( func(high)-func(low) + is_low_bujin + MOD)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, l: str, h: str) -> int:\n",
    "        a = [str(j) for j in range(10)]\n",
    "        m = 10**9 + 7\n",
    "        def g(x):\n",
    "            if x<0:\n",
    "                return 0 \n",
    "            s = str(x)\n",
    "            n = len(s)\n",
    "            @cache \n",
    "            def f(j, pre, limit):\n",
    "                if j==n:\n",
    "                    return 1 \n",
    "                ans = 0    \n",
    "                if pre==-1:\n",
    "                    # ans+=f(j+1, )\n",
    "                    # ans += f(j-1, -1, )\n",
    "                    ans += f(j+1, -1, 0) \n",
    "                    b = {j for j in a if j!='0'}\n",
    "                else:\n",
    "                    b = []\n",
    "                    x = int(pre)\n",
    "                    for y in [x-1, x+1]:\n",
    "                        if (0<=y<=9):\n",
    "                            b.append(str(y))\n",
    "                           \n",
    "                c = s[j] if limit else '9'\n",
    "                for k in b:\n",
    "                        if k<=c:                   \n",
    "                        \n",
    "                            ans+=f(j+1, k,  limit&(k==c))\n",
    "                return ans%m\n",
    "            return f(0, -1, 1)%m\n",
    "        return (g(int(h))-g(int(l)-1))%m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s:string) -> int:\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                   return int(is_num)\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low)- 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, l: str, h: str) -> int:\n",
    "        a = [str(j) for j in range(10)]\n",
    "        m = 10**9 + 7\n",
    "        def g(x):\n",
    "            if x<0:\n",
    "                return 0 \n",
    "            s = str(x)\n",
    "            n = len(s)\n",
    "            @cache \n",
    "            def f(j, pre, limit):\n",
    "                if j==n:\n",
    "                    return 1 \n",
    "                ans = 0    \n",
    "                if pre==-1:\n",
    "                    ans+=f(j+1, -1, 0) \n",
    "                    b = {j for j in a if j!='0'}\n",
    "                else:\n",
    "                    b = []\n",
    "                    x = int(pre)\n",
    "                    for y in [x-1, x+1]:\n",
    "                        if (0<=y<=9):\n",
    "                            b.append(str(y))\n",
    "                           \n",
    "                c = s[j] if limit else '9'\n",
    "                for k in b:\n",
    "                        if k<=c:                   \n",
    "                        \n",
    "                            ans+=f(j+1, k,  limit&(k==c))\n",
    "                return ans%m\n",
    "            return f(0, -1, 1)%m\n",
    "        return (g(int(h)) - g(int(l) -1))%m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def calc(s: str) -> int:\n",
    "\n",
    "            @cache  # 记忆化搜索\n",
    "\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "\n",
    "                if i == len(s):\n",
    "\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "\n",
    "                res = 0\n",
    "\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "\n",
    "                return res % MOD\n",
    "\n",
    "            return f(0, 0, True, False)\n",
    "\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        \n",
    "        def cal(n):\n",
    "            @cache\n",
    "            def f(i, pre, islimit, isnum):\n",
    "                if i == len(n):\n",
    "                    return 1 if isnum else 0\n",
    "\n",
    "                res = 0\n",
    "                if not isnum:\n",
    "                    res = (res + f(i + 1, pre, False, False)) % MOD\n",
    "\n",
    "                l = 0 if isnum else 1\n",
    "                r = int(n[i]) if islimit else 9\n",
    "                for j in range(l, r + 1):\n",
    "                    if not isnum or abs(pre - j) == 1:\n",
    "                        res = (res + f(i + 1, j, islimit and j == r, True)) % MOD\n",
    "                return res\n",
    "            \n",
    "            return f(0, 0, True, False)\n",
    "        \n",
    "        res = (cal(high) - cal(low) + MOD) % MOD\n",
    "        \n",
    "        pre = int(low[0]) - 1\n",
    "        suc = True\n",
    "        for c in low:\n",
    "            c = int(c)\n",
    "            if abs(c - pre) == 1:\n",
    "                pre = c\n",
    "            else:\n",
    "                suc = False\n",
    "                break\n",
    "        \n",
    "        if suc:\n",
    "            res = (res + 1) % MOD\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s):\n",
    "            @cache\n",
    "            def dfs(i, pre, is_limit, is_num):\n",
    "                if i == len(s):\n",
    "                    return int(is_num)\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i+1, pre, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res += dfs(i+1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return dfs(0, 0, True, False)\n",
    "        \n",
    "        return (calc(high) - calc(str(int(low)-1))) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def inner(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "\n",
    "            return f(0, 0, True, False)\n",
    "\n",
    "        return (inner(high) - inner(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        def g(s,x):\n",
    "            m = len(s)\n",
    "            if m == 0: return 1 if x >= 0 else 0\n",
    "            key = (s,x)\n",
    "            if key not in has:\n",
    "                m -= 1\n",
    "                v = int(s[0])\n",
    "                tep = 0\n",
    "                for i in dc[x]:\n",
    "                    if i < v:\n",
    "                        tep += g(\"9\"*m, i)\n",
    "                    elif i == v:\n",
    "                        tep += g(s[1:], i)\n",
    "                        break\n",
    "                    else:\n",
    "                        break\n",
    "                has[key] = tep % 1000000007\n",
    "            return has[key]\n",
    "        dc = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3, 5], 5: [4, 6], 6: [5, 7], 7: [6, 8], 8: [7, 9], 9: [8], -1: [-1, 1, 2, 3, 4, 5, 6, 7, 8, 9]}\n",
    "        has = {}\n",
    "        # g(high, -1)\n",
    "        # g(str(int(low)-1),-1)\n",
    "        # print(has)\n",
    "        return (g(high, -1) - g(str(int(low)-1),-1)) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        def cal(s : str) -> int:\n",
    "            @cache # 记忆化搜索\n",
    "            def f(i : int,pre : int,is_limit : bool,is_num : bool) -> int:\n",
    "                \"\"\"\n",
    "                i: 当前数位\n",
    "                pre: 上一位填的数字(约束条件为相邻数位差值限制)\n",
    "                is_limit: 前面填的数字是否都是n对应位上的，若为true，即受到约束，那么当前位至多填int(s[i])，否则至多为9\n",
    "                is_num: 前面是否填了数字，用于判断是否跳过，若为true，那么当前位可以从0开始，否则可以选择继续跳过，或从1开始填数字\n",
    "                return: 返回从i开始填数字，能构造出的特殊整数的数目\n",
    "                \"\"\"\n",
    "                if i == len(s):  # 成功构造出长为len(s)的数字 \n",
    "                    return int(is_num)  # 若is_num为True 说明所填数非全0 则得到一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 仍未填数字 可以选择继续跳过\n",
    "                    res = f(i + 1,pre,False,False)\n",
    "                low = 0 if is_num else 1  # 确定当前位能填数下界 若仍未填数值时 由于不含前导0 最小填1\n",
    "                up = int(s[i]) if is_limit else 9  # 确定当前位能填数上界 若受到is_limit约束时 最大填s[i]\n",
    "                for d in range(low,up + 1): # 枚举当前位填数\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一个填的数位不受约束 后面的需要满足相邻差为1\n",
    "                        res += f(i + 1,d,is_limit and d == up,True)\n",
    "                return res % mod\n",
    "            return f(0,0,True,False)\n",
    "\n",
    "        return (cal(high) - cal(str(int(low) - 1))) % mod # 取模得到非负余数解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        return (self.count(high) - self.count(str(int(low) - 1))) % int(1e9 + 7)\n",
    "    \n",
    "    @staticmethod\n",
    "    def count(n):\n",
    "        k = len(n)\n",
    "        # if prev_num == 10, not a number\n",
    "        @cache\n",
    "        def dfs(pos, prev_num, is_limit):\n",
    "            if pos == k:\n",
    "                return prev_num != 10\n",
    "            ans = 0\n",
    "            up = 9 if not is_limit else int(n[pos])\n",
    "            ds = [prev_num - 1, prev_num + 1]\n",
    "            if prev_num == 10:\n",
    "                ans += dfs(pos + 1, prev_num, False)\n",
    "                ds = list(range(1, 10))\n",
    "            for d in ds:\n",
    "                if 0 <= d <= up:\n",
    "                    ans += dfs(pos + 1, d, is_limit and d == int(n[pos]))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 10, True) % int(1e9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "       def cal(s: str) -> int:\n",
    "          @cache\n",
    "          def dfs(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "             if i == n:\n",
    "                return is_num\n",
    "             res = 0\n",
    "             if not is_num:\n",
    "                res += dfs(i + 1, pre, False, False)\n",
    "                res %= MOD\n",
    "             up = int(s[i]) if is_limit else 9\n",
    "             for j in range(0 if is_num else 1, up + 1):\n",
    "                if not is_num or abs(j - pre) == 1:\n",
    "                   res += dfs(i + 1, j, is_limit and j == up, True)\n",
    "                   res %= MOD\n",
    "             return res % MOD\n",
    "          n = len(s)\n",
    "          return dfs(0, 0, True, False)\n",
    "       MOD = 10 ** 9 + 7\n",
    "       return (cal(high) - cal(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        def cal(s : str) -> int:\n",
    "            @cache # 记忆化搜索\n",
    "            def f(i : int,pre : int,is_limit : bool,is_num : bool) -> int:\n",
    "                \"\"\"\n",
    "                i: 当前数位\n",
    "                pre: 上一位填的数字(约束条件为相邻数位差值限制)\n",
    "                is_limit: 前面填的数字是否都是n对应位上的，若为true，即受到约束，那么当前位至多填int(s[i])，否则至多为9\n",
    "                is_num: 前面是否填了数字，用于判断是否跳过，若为true，那么当前位可以从0开始，否则可以选择继续跳过，或从1开始填数字\n",
    "                return: 返回从i开始填数字，能构造出的特殊整数的数目\n",
    "                \"\"\"\n",
    "                if i == len(s):  # 成功构造出长为len(s)的数字 \n",
    "                    return int(is_num)  # 若非全0 返回1\n",
    "                res = 0\n",
    "                if not is_num:  # 仍未填数字 可以选择继续跳过\n",
    "                    res = f(i + 1,pre,False,False)\n",
    "                low = 0 if is_num else 1  # 确定当前位能填数下界 仍未填数值时 由于不含前导0 最小填1\n",
    "                up = int(s[i]) if is_limit else 9  # 确定当前位能填数上界 受到is_limit约束时 最大填s[i]\n",
    "                for d in range(low,up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一个填的数位不受约束 后面的需要满足相邻差为1\n",
    "                        res += f(i + 1,d,is_limit and d == up,True)\n",
    "                return res % mod\n",
    "            return f(0,0,True,False)\n",
    "\n",
    "        return (cal(high) - cal(str(int(low) - 1))) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s):\n",
    "            @cache\n",
    "            def dfs(i, pre, is_limit, is_num):\n",
    "                if i == len(s): return int(is_num)\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res += dfs(i + 1, d, is_limit and d == up, True) % MOD\n",
    "                return res % MOD\n",
    "            return dfs(0, 0, True, False)\n",
    "        return (cal(high) - cal(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "       def cal(s: str) -> int:\n",
    "          @cache\n",
    "          def dfs(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "             if i == n:\n",
    "                return is_num\n",
    "             res = 0\n",
    "             if not is_num:\n",
    "                res += dfs(i + 1, pre, False, False)\n",
    "                res %= MOD\n",
    "             up = int(s[i]) if is_limit else 9\n",
    "             for j in range(0 if is_num else 1, up + 1):\n",
    "                if pre == 10 or abs(j - pre) == 1:\n",
    "                   res += dfs(i + 1, j, is_limit and j == up, True)\n",
    "                   res %= MOD\n",
    "             return res\n",
    "          n = len(s)\n",
    "          return dfs(0, 10, True, False)\n",
    "       MOD = 10 ** 9 + 7\n",
    "       return (cal(high) - cal(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: string) -> int:\n",
    "            n = len(s)\n",
    "            @cache\n",
    "            def dfs(i:int,last:int,is_digit:bool,is_num:bool)->int:\n",
    "                if i == n:\n",
    "                    return is_num\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i + 1,last,False,False)\n",
    "                up = int(s[i]) if is_digit else 9\n",
    "                for d in range(1 - is_num,up + 1):\n",
    "                    if not is_num or abs(d - last) == 1: \n",
    "                        res += dfs(i + 1,d,is_digit and d == up,True)\n",
    "                return res % MOD\n",
    "            return dfs(0,0,True,False)\n",
    "        return (cal(high) - cal(str(int(low) - 1)) + MOD) % MOD # + check(low)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            # 数位DP记忆化搜索\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) ->int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)\n",
    "                res = 0\n",
    "                # 前面没填数, 可以跳过当前位\n",
    "                if not is_num:\n",
    "                    res += f(i+1, pre, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                # 枚举下一位\n",
    "                for d in range(low, up + 1):\n",
    "                    # 第一位数字随便填, 其它必须相差1\n",
    "                    if not is_num or abs(pre - d) == 1:\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        # 长度为l，首位为a，且小于等于s（长度也为l）的步进数字个数\n",
    "        @cache\n",
    "        def dp(l, a, s):\n",
    "            if not 0 <= a <= min(int(s[0]), 9):\n",
    "                return 0\n",
    "            if l == 1:\n",
    "                return 1\n",
    "            ret = dp(l - 1, a - 1, s[1:] if a == int(s[0]) else '9' * (l - 1)) + dp(l - 1, a + 1, s[1:] if a == int(s[0]) else '9' * (l - 1))\n",
    "            return ret % MOD\n",
    "        \n",
    "        # 小于等于s的步进数字个数\n",
    "        def noGreater(s):\n",
    "            l = len(s)\n",
    "            if l == 1:\n",
    "                return int(s)\n",
    "            \n",
    "            ret = sum(dp(ll, a, '9' * ll) for ll in range(1, l) for a in range(1, 10)) % MOD  # 长度小于l的所有步进数字\n",
    "            # 遍历步进数字的首位\n",
    "            for a in range(1, int(s[0]) + 1):\n",
    "                ret += dp(l - 1, a - 1, s[1:] if a == int(s[0]) else '9' * (l - 1)) + dp(l - 1, a + 1, s[1:] if a == int(s[0]) else '9' * (l - 1))\n",
    "            return ret % MOD\n",
    "        \n",
    "        return (noGreater(high) - noGreater(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return 1  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/count-stepping-numbers-in-range/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "\n",
    "        MODX = 10**9 +7\n",
    "\n",
    "\n",
    "        def f(nums):\n",
    "            @lru_cache(None)\n",
    "            def DFS(i,is_limit, pre_zero,pre_val):\n",
    "                if i==len(nums):\n",
    "                    return 1\n",
    "                \n",
    "                ans = 0\n",
    "                if pre_zero:\n",
    "                    ans += DFS(i+1,False,True,0)\n",
    "                \n",
    "                up = 9 if not is_limit else int(nums[i])\n",
    "                for x in range(up+1):\n",
    "                    if pre_zero:\n",
    "                        if x==0:\n",
    "                            continue\n",
    "                        else:\n",
    "                            ans += DFS(i+1,is_limit and x==up, False,x)\n",
    "\n",
    "                    else: \n",
    "                        if abs(x-pre_val)!=1:\n",
    "                            continue \n",
    "                        ans += DFS(i+1,is_limit and x==up, False, x)\n",
    "                return ans%MODX \n",
    "                    \n",
    "            \n",
    "\n",
    "            return DFS(0,True,True,0)\n",
    "        \n",
    "        ans = f(high)-f(low)\n",
    "\n",
    "        flag = True \n",
    "        for i in range(1,len(low)):\n",
    "            if abs(int(low[i])-int(low[i-1]))!=1:\n",
    "                flag = False \n",
    "                break \n",
    "        \n",
    "        return (ans + int(flag))%MODX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        \n",
    "        def check(s):\n",
    "            m=len(s)\n",
    "            if m==1:return True\n",
    "            for i in range(m-1):\n",
    "                if abs(int(s[i])-int(s[i+1]))!=1:return False\n",
    "            return True\n",
    "        mod=10**9+7\n",
    "        def get(s):\n",
    "            m=len(s)\n",
    "\n",
    "            @cache\n",
    "            def dfs(cur,is_lim,is_num,pre):\n",
    "                if cur==m:\n",
    "                    return int(is_num)\n",
    "\n",
    "                ans=0\n",
    "                if not is_num:\n",
    "                    ans+= dfs(cur+1,False,False,pre)\n",
    "                low=1-int(is_num)\n",
    "                up=int(s[cur]) if is_lim else 9\n",
    "                for i in range(low,up+1):\n",
    "                    if  pre is None or abs(i-pre)==1:\n",
    "                        ans+=dfs(cur+1,is_lim and i==up,True,i)\n",
    "                return ans%mod\n",
    "\n",
    "            return dfs(0,True,False,None)\n",
    "        a=get(low)\n",
    "        b=get(high)\n",
    "        print(a,b)\n",
    "        return (b-a+int(check(low)))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s):\n",
    "            @cache\n",
    "            def f(i, pre, is_limit, is_num):\n",
    "                if i == len(s):\n",
    "                    return int(is_num)\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0 , True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def calc(s: str) -> int:\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  \n",
    "                res = 0\n",
    "                if not is_num:  \n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  \n",
    "                up = int(s[i]) if is_limit else 9  \n",
    "                for d in range(low, up + 1): \n",
    "                    if not is_num or abs(d - pre) == 1:  \n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "\n",
    "            return f(0, 0, True, False)\n",
    "\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        def cal(s : str) -> int:\n",
    "            @cache\n",
    "            def f(i : int,pre : int,is_limit : bool,is_num : bool) -> int:\n",
    "                \"\"\"\n",
    "                s: 处理数字字符串\n",
    "                i: 当前数位\n",
    "                pre: 上一位填的数字(约束条件为相邻数位差值限制)\n",
    "                is_limit: 前面填的数字是否都是n对应位上的，若为true，即受到约束，那么当前位至多填int(s[i])，否则至多为9\n",
    "                is_num: 前面是否填了数字，用于判断是否跳过，若为true，那么当前位可以从0开始，否则可以选择继续跳过，或从1开始填数字\n",
    "                return: 返回从i开始填数字，能构造出的特殊整数的数目\n",
    "                \"\"\"\n",
    "                if i == len(s):  # 成功构造出长为len(s)的数字 \n",
    "                    return int(is_num)  # 若不为0(已填数字) 返回1\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1,pre,False,False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low,up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一个数位不受约束 后面的需要满足相邻差为1\n",
    "                        res += f(i + 1,d,is_limit and d == up,True)\n",
    "                return res % mod\n",
    "            return f(0,0,True,False)\n",
    "\n",
    "        return (cal(high) - cal(str(int(low) - 1))) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def calc(s: str) -> int:\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  \n",
    "                res = 0\n",
    "                if not is_num:  \n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  \n",
    "                up = int(s[i]) if is_limit else 9  \n",
    "                for d in range(low, up + 1): \n",
    "                    if not is_num or abs(d - pre) == 1:  \n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "\n",
    "            return f(0, 0, True, False)\n",
    "\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        M = int(1e9 + 7)\n",
    "        def calc(high):\n",
    "            high = list(map(int, str(high)))\n",
    "            # print(high)\n",
    "            @cache\n",
    "            def search(pos, cur, is_limit, is_valid):\n",
    "                # print(pos, cur, is_limit, is_valid)\n",
    "                if pos >= len(high) - 1:\n",
    "                    # print(pos, cur, is_limit, is_valid, 1)\n",
    "                    return 1\n",
    "                ans = 0\n",
    "                _next = high[pos + 1]\n",
    "                if cur == 0:\n",
    "                    if is_valid:\n",
    "                        if not is_limit or _next > 0:\n",
    "                            ans = (ans + search(pos + 1, 1, is_limit and _next == 1, True)) % M\n",
    "                    else:\n",
    "                        for i in range(10):\n",
    "                            ans = (ans + search(pos + 1, i, False, i != 0)) % M\n",
    "                else:\n",
    "                    if is_limit:\n",
    "                        if cur + 1 <= _next:\n",
    "                            ans = (ans + search(pos + 1, cur + 1, cur + 1 == _next, True)) % M\n",
    "                        if cur - 1 <= _next:\n",
    "                            ans = (ans + search(pos + 1, cur - 1, cur - 1 == _next, True)) % M\n",
    "                    else:\n",
    "                        ans = (ans + search(pos + 1, cur - 1, False, True)) % M\n",
    "                        if cur < 9:\n",
    "                            ans = (ans + search(pos + 1, cur + 1, False, True)) % M\n",
    "                # print(pos, cur, is_limit, is_valid, ans)\n",
    "                return ans\n",
    "            first = int(high[0])\n",
    "            ans = 0\n",
    "            for i in range(first + 1):\n",
    "                ans = (ans + search(0, i, i == first, i != 0)) % M\n",
    "            # print(\"FUCK\", ans)\n",
    "            return ans\n",
    "        return (calc(int(high)) - calc(int(low) - 1) + M) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        def calc(s: str) -> int:\n",
    "            @functools.cache\n",
    "            def dfs(i: int, pre: int, isLimit: bool, isNum: bool) -> int:\n",
    "                \"\"\"表示构造第 i 位及其之后数位的合法方案数\"\"\"\n",
    "                if i == len(s):\n",
    "                    return int(isNum)  # isNum 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not isNum:  # 可以跳过当前数位\n",
    "                    res = dfs(i + 1, pre, False, False)\n",
    "                down = 0 if isNum else 1  # 如果前面没有填数字, 必须从 1 开始, 因为不能有前导零\n",
    "                # 如果前面填的数字都和 s 的一样, 那么这一位至多填 s[i], 否则就超过 s 了\n",
    "                up = int(s[i]) if isLimit else 9\n",
    "                for d in range(down, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not isNum or abs(d - pre) == 1:  # 第一位数字随便填, 其余必须相差 1\n",
    "                        res += dfs(i + 1, d, isLimit and d == up, True)\n",
    "                return res % mod\n",
    "\n",
    "            return dfs(0, 0, True, False)\n",
    "\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7 \n",
    "        def calc(s: str) -> int:\n",
    "            @cache ## 記憶化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num) # is_num 為 true 表示得到了一個合法數字\n",
    "                res = 0\n",
    "                if not is_num: # 可以跳過當前數位\n",
    "                    res = f(i+1, pre, False, False)\n",
    "                low = 0 if is_num else 1 # 如果前面沒有填數字，必須從 1 開始（因為不能有前導零）\n",
    "                up = int(s[i]) if is_limit else 9 # 如果前面填的數字都和 n 一樣，那麼這一位至多填 s[i] （否則就超過n啦）\n",
    "\n",
    "                for d in range(low, up+1): # 枚舉要填入的數字d\n",
    "                    if not is_num or abs(d - pre) == 1: # 第一數位隨便填，後面的 abs = 1\n",
    "                        res += f(i+1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#统计范围内的步进数字数目,数位dp，记忆化搜索，输入：low = \"1\", high = \"11\",输出：10;输入：low = \"90\", high = \"101\",输出：2\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @functools.lru_cache(None)  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  res = f(i + 1, pre, False, False)# 可以跳过当前数位\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache\n",
    "            def dfs(i: int, pre: int, is_limit: bool, is_num: bool):\n",
    "                if i == len(s):\n",
    "                    return is_num\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i + 1, pre, False, False)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(1 - int(is_num), up + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res += dfs(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return dfs(0, 0, True, False) \n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: str):\n",
    "            m = len(s)\n",
    "            # dp = [[-1] * 10 for _ in range(m)]\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return int(is_num)\n",
    "                # if not is_limit and is_num and dp[i][pre] != -1:\n",
    "                #     return dp[i][pre]\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[i]) if is_limit else 9\n",
    "                for d in range(l, r + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res = (res + f(i + 1, d, is_limit and (d == int(s[i])), True)) % MOD\n",
    "                # if not is_limit and is_num:\n",
    "                #     dp[i][pre] = res\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return ((cal(high) - cal(str(int(low) - 1))) % MOD + MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(s: str):\n",
    "            m = len(s)\n",
    "            # dp = [[-1] * 10 for _ in range(m)]\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return int(is_num)\n",
    "                # if not is_limit and is_num and dp[i][pre] != -1:\n",
    "                #     return dp[i][pre]\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[i]) if is_limit else 9\n",
    "                for d in range(l, r + 1):\n",
    "                    if not is_num or abs(d - pre) == 1:\n",
    "                        res = (res + f(i + 1, d, is_limit and (d == int(s[i])), True)) % MOD\n",
    "                # if not is_limit and is_num:\n",
    "                #     dp[i][pre] = res\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        return ((cal(high) - cal(str(int(low) - 1))) % MOD + MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s):\n",
    "            n = len(s)\n",
    "            @cache\n",
    "            def dfs(i, pre, isLimit, isNum):\n",
    "                if i==n:\n",
    "                    return int(isNum)\n",
    "                res = 0\n",
    "                # 可以跳过当前位置\n",
    "                if not isNum:\n",
    "                    res += dfs(i+1, pre, False, False)\n",
    "                low = 0 if isNum else 1 # 如果前面没有数字，那么必须从1开始\n",
    "                high = int(s[i]) if isLimit else 9 # 如果前面达到上限，当前最多填s[i]\n",
    "                for d in range(low, high+1):\n",
    "                    if (not isNum) or abs(d-pre)==1:\n",
    "                        res += dfs(i+1, d, isLimit and d==high, True)\n",
    "                return res\n",
    "            return dfs(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low)-1)) ) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def check(s: str) -> bool:\n",
    "            return all(abs(int(i) - int(j)) == 1 for i, j in pairwise(s))\n",
    "        def calc(s: int) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, prev: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, prev, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "                for digit in range(low, up + 1):\n",
    "                    if prev == -1 or abs(digit - prev) == 1:  # 枚举要填入的数字 digit\n",
    "                        res += f(i + 1, digit, is_limit and digit == up, True)\n",
    "                return res\n",
    "            return f(0, -1, True, False)\n",
    "        return (calc(high) - calc(low) + int(check(low))) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        # 模板：数位DP容斥模板题\n",
    "\n",
    "        def check(num):\n",
    "            @lru_cache(None)\n",
    "            def dfs(i, is_limit, is_num, pre):\n",
    "                if i == n:\n",
    "                    return is_num\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res += dfs(i + 1, False, 0, -1)\n",
    "\n",
    "                floor = 0 if is_num else 1\n",
    "                ceil = int(s[i]) if is_limit else 9\n",
    "                for x in range(floor, ceil + 1):\n",
    "                    if pre == -1 or abs(x - pre) == 1:\n",
    "                        res += dfs(i + 1, is_limit and ceil == x, 1, x)\n",
    "                return res\n",
    "        \n",
    "            s = str(num)\n",
    "            n = len(s)\n",
    "            return dfs(0, True, 0, -1)\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        return (check(int(high)) - check(int(low)-1)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def f(s: string) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, p,is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, p,False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or p-d in (-1,1):\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res\n",
    "            return f(0,-1,True, False)\n",
    "        b=True\n",
    "        ans = f(high) - f(str(int(low)-1)) \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        def calc(s: str) -> int:\n",
    "            @cache\n",
    "            def f(i: int, pre: int, is_limit: bool, is_nums: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return is_nums\n",
    "                res = 0\n",
    "                if not is_nums:\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_nums else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    if not is_nums or abs(d - pre) == 1:\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res\n",
    "            return f(0, 0, True, False)\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def calc(s: str) -> int:\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return 1 if is_num else 5  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, pre, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1\n",
    "                        res += f(i + 1, d, is_limit and d == up, True)\n",
    "                return res % MOD\n",
    "            return f(0, 0, True, False)\n",
    "        print(calc(high), calc(str(int(low))))\n",
    "        return (calc(high) - calc(str(int(low) - 1))) % MOD\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/count-stepping-numbers-in-range/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index:int, chosen_num:int, reach_limit:bool, num_chosen_before:bool, limit_num_str:str) -> int:\n",
    "            if index == len(limit_num_str):\n",
    "                return 1 if num_chosen_before else 0\n",
    "            \n",
    "            ans = 0\n",
    "            if not num_chosen_before:\n",
    "                ans = (ans + dfs(index + 1, chosen_num, False, False, limit_num_str)) % MOD\n",
    "            \n",
    "            high = int(limit_num_str[index]) if reach_limit else 9\n",
    "            low = 0 if num_chosen_before else 1\n",
    "            for i in range(low, high + 1):\n",
    "                if chosen_num == -1 or i == chosen_num - 1 or i == chosen_num + 1:\n",
    "                    ans = (ans + dfs(index + 1, i, reach_limit & (i == high), True, limit_num_str)) % MOD\n",
    "            return ans\n",
    "        \n",
    "        return (dfs(0, -1, True, False, high) - dfs(0, -1, True, False, str(int(low) - 1)) + MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        @cache\n",
    "        def dfs(pos, s, limit, isnum, pre):\n",
    "            if pos == len(s):\n",
    "                return int(isnum)\n",
    "            low = 0\n",
    "            if not isnum:\n",
    "                low = 1\n",
    "            high = 9\n",
    "            if limit:\n",
    "                high = int(s[pos])\n",
    "            res = 0\n",
    "            if not isnum:\n",
    "                res = dfs(pos + 1, s, False, False, -1)\n",
    "            for i in range(low, high + 1):\n",
    "                if pre == -1 or abs(i - pre) == 1:\n",
    "                    res += dfs(pos + 1, s, limit and i == high, True, i)\n",
    "            return res % int(1e9 + 7)\n",
    "        x = dfs(0, high, True, False, -1)\n",
    "        y = dfs(0, str(int(low) - 1), True, False, -1)\n",
    "        return (x - y) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        low = str(int(low)-1)\n",
    "        mod = int(1e9+7)\n",
    "        @cache\n",
    "        def f(i: int, pre: int, limit: bool, isNum: bool, s: str) -> int:\n",
    "            if i == len(s):\n",
    "                return int(isNum)\n",
    "            ans = 0\n",
    "            if not isNum:\n",
    "                ans = f(i+1,pre,False,False,s)\n",
    "            up = int(s[i]) if limit else 9\n",
    "            for d in range(1 - int(isNum), up+1):\n",
    "                if abs(d - pre) == 1 or pre == -1:\n",
    "                    ans += f(i+1, d, limit and d == up, True, s)\n",
    "                    ans %= mod\n",
    "            return ans\n",
    "        return ( f(0,-1,True, False,high) - f(0,-1,True,False,low) +mod ) %mod\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        @lru_cache(maxsize = None)\n",
    "        def f(i, is_limit, is_num, a, s):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1, False, False, a, s)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1 - int(is_num), up + 1):\n",
    "                if i == 0 or not is_num:\n",
    "                    res += f(i + 1, is_limit and (d == up), True, d, s)\n",
    "                elif abs(a - d) == 1:\n",
    "                    res += f(i + 1, is_limit and (d == up), True, d, s)\n",
    "            return res % int(1e9 + 7)\n",
    "        low = str(int(low) - 1)\n",
    "        cnt2 = f(0, True, False, -1, high)\n",
    "        cnt1 = f(0, True, False, -1, low)\n",
    "        return (cnt2 - cnt1) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        @cache\n",
    "        def help(sb,i,k,islimit,isnum):\n",
    "            if i==len(sb):\n",
    "                if isnum:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res=0\n",
    "            if not isnum:\n",
    "                res+=help(sb,i+1,0,False,False)\n",
    "            mi=0 if isnum else 1\n",
    "            ma=int(sb[i]) if islimit else 9\n",
    "            for j in range(mi,ma+1):\n",
    "                if abs(j-k)==1 or isnum==False:\n",
    "                    res+=help(sb,i+1,j,islimit and j==ma,True)\n",
    "            return res%1000000007\n",
    "        temp=1\n",
    "        for i,j in pairwise(low):\n",
    "            if abs(int(j)-int(i))!=1:\n",
    "                temp=0\n",
    "                break\n",
    "        return (help(high,0,0,True,False)-help(low,0,0,True,False)+temp)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        h = tuple(map(int, high))\n",
    "        l = tuple(map(int, str(int(low)-1)))\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, is_limit, is_num, pre, arr):\n",
    "            if idx == len(arr): return int(is_num)\n",
    "            ret = 0\n",
    "            if not is_num:\n",
    "                ret += dfs(idx + 1, False, False, -1, arr)\n",
    "            nums = []\n",
    "            up = arr[idx] if is_limit else 9\n",
    "            if pre == -1:\n",
    "                nums = [i for i in range(1, 10 if not is_limit else arr[idx] + 1)]\n",
    "            else:\n",
    "                if pre > 0 and pre - 1 <= up: nums.append(pre - 1)\n",
    "                if pre < up: nums.append(pre + 1)\n",
    "            for num in nums:\n",
    "                ret += dfs(idx + 1, is_limit and num == arr[idx], True, num, arr)\n",
    "            return ret\n",
    "\n",
    "        return (dfs(0, True, False, -1, h) - dfs(0, True, False, -1, l) + MOD) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        @lru_cache(maxsize = None)\n",
    "        def f(i, is_limit, is_num, a, s):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1, False, False, a, s)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1 - int(is_num), up + 1):\n",
    "                if i == 0 or not is_num:\n",
    "                    res += f(i + 1, is_limit and (d == up), True, d, s)\n",
    "                elif abs(a - d) == 1:\n",
    "                    res += f(i + 1, is_limit and (d == up), True, d, s)\n",
    "            return res\n",
    "        low = str(int(low) - 1)\n",
    "        cnt2 = f(0, True, False, -1, high)\n",
    "        cnt1 = f(0, True, False, -1, low)\n",
    "        return (cnt2 - cnt1) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        @lru_cache(maxsize = None)\n",
    "        def f(i, is_limit, is_num, a, s):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1, False, False, a, s)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1 - int(is_num), up + 1):\n",
    "                if i == 0 or not is_num:\n",
    "                    res += f(i + 1, is_limit and (d == up), True, d, s)\n",
    "                elif abs(a - d) == 1:\n",
    "                    res += f(i + 1, is_limit and (d == up), True, d, s)\n",
    "            return res\n",
    "        low = str(int(low) - 1)\n",
    "        cnt2 = f(0, True, False, -1, high)\n",
    "        cnt1 = f(0, True, False, -1, low)\n",
    "        return (cnt2 - cnt1) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: str, high: str) -> int:\n",
    "        @cache\n",
    "        def f(i: int, s: str, pre: int, islimit: bool, isnum: bool):\n",
    "            if i == len(s):\n",
    "                return isnum\n",
    "            res = 0\n",
    "            if not isnum:\n",
    "                res = f(i + 1, s, pre, False, False)\n",
    "            up = int(s[i]) if islimit else 9\n",
    "            for d in range(1 - int(isnum), up + 1):\n",
    "                if not isnum:\n",
    "                    res += f(i + 1, s, d, islimit and d == up, True)\n",
    "                else:\n",
    "                    if abs(d - pre) == 1:\n",
    "                        res += f(i + 1, s, d, islimit and d == up, True)\n",
    "            return res\n",
    "        return (f(0, high, -1, True, False) - f(0, str(int(low) - 1), -1, True, False)) % MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
